"""
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:
        输入: k = 3, n = 7
        输出: [[1,2,4]]
        解释:
        1 + 2 + 4 = 7
        没有其他符合的组合了。
"""
tem = []
ans = []
k = 3
n = 9


def backtracking(k, n, height, MySum):
    if len(tem) == k and MySum == n:
        ans.append(tem.copy())
        return
    if len(tem) == k or MySum > n:
        return
    for i in range(height, 10):
        MySum += i
        tem.append(i)
        backtracking(k, n, i + 1, MySum)
        MySum -= tem.pop()
    return


backtracking(k, n, 1, 0)
print(ans)
